Class sjl.Deque
All Packages Class Hierarchy This Package Previous Next Index
Class sjl.Deque
java.lang.Object
|
+----sjl.Deque
- public class Deque
- extends Object
- implements ReversibleContainer, QueueContainer
Deque
is a kind of sequence that, like vector, supports
random access iterators.
In additition it supports constant time insert and erase operations at
the beginning or the end; insert and erase in the middle take linear time.
As with vectors, storage management is handled automatically.
insert
and push
invalidates all the iterators
and references to the deque.
In the worst case, inserting a single element into a deque takes time
linear in the minimum of the distance from the insertion point to the
beginning of the deque and the distance from the insertion point to
the end of the deque.
Inserting a single element either at the beginning or at the end of a
deque always takes constant time. That is, a deque is especially
optimized for pushing and popping elements at the beginning and end.
erase
and pop
invalidates all the iterators
and references to deque.
Copyright © 1996 Finn Bock
-
buffer_size
- Private.
-
BufferSize
- The size of the second level buffer.
-
map
- Private.
-
map_size
- Private.
-
MapSize
- The size of the first level array.
-
Deque()
- Construct a new empty Deque.
-
Deque(Deque)
- Construct a new Deque with the size and contents of another deque.
-
Deque(ForwardIterator, ForwardIterator)
- Construct a new Deque with the contents of the
range
[first,last)
.
-
Deque(int, Object)
- Construct a new Deque with an initial size of
size
elements,
each element initialized to with a reference to value.
-
back()
- Return the last element in the container.
-
begin()
- Returns the iterator that represents the beginning of the deque.
-
beginGeneric()
- Returns the iterator that represents the beginning of the deque as
an untyped iterator.
-
beginRef()
- Returns a reference to the iterator that represents the beginning of
the deque.
-
empty()
- Returns
true
if the deque does not contain any elements.
-
end()
- Returns the iterator that represents the end of the deque.
-
endGeneric()
- Returns the iterator that represents the end of the deque as
an untyped iterator.
-
endRef()
- Returns a reference to the iterator that represents the end of
the deque.
-
equals(Object)
- Compare the elements in this container with the elements
in another container.
-
erase(Iterator)
- Removes the element specified by position.
-
erase(Iterator, Iterator)
- Removes the elements in the specified range.
-
flush()
- Erase all the elements in the container.
-
front()
- Return the first element in the container.
-
get(int)
- Returns the
n
th element in the container.
-
insert(Iterator, InputIterator, InputIterator)
- The elements in the range
[first,last)
are inserted
into deque at the specified position.
-
insert(Iterator, int, Object)
- Insert n references to element into the deque at the specified position.
-
insert(Iterator, Object)
- Insert an element into the deque at the specified position.
-
max_size()
- Returns the maximum number of elements that can be stored in a deque.
-
pop_back()
- Removes the last element in deque.
-
pop_front()
- Removes the first element in deque.
-
push_back(Object)
- Add an element to the end of the deque.
-
push_front(Object)
- Add an element to the front of the deque.
-
put(int, Object)
- Set the
n
th element in the container to o.
-
rbegin()
- Returns a copy of the reverse iterator that represents the
beginning (end) of the list.
-
rbeginGeneric()
- Returns a copy of the reverse iterator that represents the
beginning (end) of the list as an untyped Iterator.
-
rend()
- Returns a copy of the iterator that represents the end (beginning)
of the list.
-
rendGeneric()
- Returns a copy of the iterator that represents the end (beginning)
of the list as an untyped Iterator.
-
size()
- Returns the number of elements stored in the deque.
-
toString()
- Returns the string representation of this deque.
MapSize
public static int MapSize
- The size of the first level array. All new Deque containers are created
with an initial map with a size of
MapSize
. The default
value is 256.
BufferSize
public static int BufferSize
- The size of the second level buffer. All new Deque containers are
created with buffers with a size of
BufferSize
. The default
value is 256.
map
protected Object map[][]
- Private. The actual data array.
map_size
protected int map_size
- Private. The actual map size.
buffer_size
protected int buffer_size
- Private. The actual buffer size.
Deque
public Deque()
- Construct a new empty Deque.
Deque
public Deque(int size,
Object value)
- Construct a new Deque with an initial size of
size
elements,
each element initialized to with a reference to value.
- Parameters:
- size - The size of the new deque.
- value - The initial value of each element in the deque.
Deque
public Deque(Deque deque)
- Construct a new Deque with the size and contents of another deque.
- Parameters:
- deque - The deque which is copied into the new deque.
Deque
public Deque(ForwardIterator first,
ForwardIterator last)
- Construct a new Deque with the contents of the
range
[first,last)
.
- Parameters:
- first - The beginning of the range.
- last - The end of the range.
flush
public void flush()
- Erase all the elements in the container.
equals
public boolean equals(Object container)
- Compare the elements in this container with the elements
in another container.
- Returns:
-
true
is the elements match.
- Overrides:
- equals in class Object
begin
public DequeIterator begin()
- Returns the iterator that represents the beginning of the deque.
beginRef
public DequeIterator beginRef()
- Returns a reference to the iterator that represents the beginning of
the deque.
end
public DequeIterator end()
- Returns the iterator that represents the end of the deque.
endRef
public DequeIterator endRef()
- Returns a reference to the iterator that represents the end of
the deque.
beginGeneric
public ForwardIterator beginGeneric()
- Returns the iterator that represents the beginning of the deque as
an untyped iterator.
endGeneric
public ForwardIterator endGeneric()
- Returns the iterator that represents the end of the deque as
an untyped iterator.
rbegin
public ReverseRandomIterator rbegin()
- Returns a copy of the reverse iterator that represents the
beginning (end) of the list.
rend
public ReverseRandomIterator rend()
- Returns a copy of the iterator that represents the end (beginning)
of the list.
rbeginGeneric
public Iterator rbeginGeneric()
- Returns a copy of the reverse iterator that represents the
beginning (end) of the list as an untyped Iterator.
rendGeneric
public Iterator rendGeneric()
- Returns a copy of the iterator that represents the end (beginning)
of the list as an untyped Iterator.
size
public int size()
- Returns the number of elements stored in the deque.
max_size
public int max_size()
- Returns the maximum number of elements that can be stored in a deque.
empty
public boolean empty()
- Returns
true
if the deque does not contain any elements.
get
public Object get(int n)
- Returns the
n
th element in the container.
put
public Object put(int n,
Object o)
- Set the
n
th element in the container to o.
front
public Object front()
- Return the first element in the container.
back
public Object back()
- Return the last element in the container.
push_front
public void push_front(Object o)
- Add an element to the front of the deque.
push_back
public void push_back(Object o)
- Add an element to the end of the deque.
pop_front
public void pop_front()
- Removes the first element in deque.
pop_back
public void pop_back()
- Removes the last element in deque.
insert
public Iterator insert(Iterator position,
Object o)
- Insert an element into the deque at the specified position.
Elements located after the position are moved.
- Parameters:
- position - insert the element at this position.
- o - the element to insert.
- Returns:
- An iterator to the position where the element was inserted.
insert
public void insert(Iterator position,
int n,
Object o)
- Insert n references to element into the deque at the specified position.
Elements located after the position are moved.
- Parameters:
- position - insert the element at this position.
- n - the number of elements to insert.
- o - the element to insert.
insert
public void insert(Iterator position,
InputIterator first,
InputIterator last)
- The elements in the range
[first,last)
are inserted
into deque at the specified position.
Elements located after the position are moved.
- Parameters:
- position - insert the element at this position.
- first - the beginning of the range.
- last - the end of the range.
erase
public void erase(Iterator position)
- Removes the element specified by position.
erase
public void erase(Iterator first,
Iterator last)
- Removes the elements in the specified range.
- Parameters:
- first - the beginning of the range.
- last - the end of the range.
toString
public String toString()
- Returns the string representation of this deque.
- Overrides:
- toString in class Object
All Packages Class Hierarchy This Package Previous Next Index